package Hard;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

// 778. 水位上升的泳池中游泳
public class Solution778 {

    class Node {
        int x;
        int y;
        int weight;

        Node(int x, int y, int weight) {
            this.x = x;
            this.y = y;
            this.weight = weight;
        }
    }

    public int swimInWater(int[][] grid) {
        // 使用迪杰斯特拉算法的思路，每次选一个最小边，当右下角那个点被遍历时，结束程序
        int min = grid[0][0];
        // 待遍历的集合
        Queue<Node> priOrityQueue = new PriorityQueue<Node>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.weight - o2.weight;
            }
        });
        int N = grid.length;
        // 已遍历的集合(指已经放在队列里)
        int valid[][] = new int[N][N];
        valid[0][0] = 1;
        priOrityQueue.offer(new Node(0, 1, grid[0][1]));
        priOrityQueue.offer(new Node(1, 0, grid[1][0]));
        valid[0][1] = 1;
        valid[1][0] = 1;
        // 初始化完毕

        while (!priOrityQueue.isEmpty()) {
            Node node = priOrityQueue.poll();
            min = Math.max(min, node.weight);
            if (node.x == N - 1 && node.y == N - 1)
                break;
            if (node.x - 1 >= 0 && valid[node.x - 1][node.y] == 0) {
                priOrityQueue.offer(new Node(node.x - 1, node.y, grid[node.x - 1][node.y]));
                valid[node.x - 1][node.y] = 1;
            }
            if (node.x + 1 < N && valid[node.x + 1][node.y] == 0) {
                priOrityQueue.offer(new Node(node.x + 1, node.y, grid[node.x + 1][node.y]));
                valid[node.x + 1][node.y] = 1;
            }
            if (node.y - 1 >= 0 && valid[node.x][node.y - 1] == 0) {
                priOrityQueue.offer(new Node(node.x, node.y - 1, grid[node.x][node.y - 1]));
                valid[node.x][node.y - 1] = 1;
            }
            if (node.y + 1 < N && valid[node.x][node.y + 1] == 0) {
                priOrityQueue.offer(new Node(node.x, node.y + 1, grid[node.x][node.y + 1]));
                valid[node.x][node.y + 1] = 1;
            }
        }
        return min;
    }
}
